#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

// longest common subsequence
size_t lcs(const char* str1, const char* str2) {
  size_t len1 = strlen(str1);
  size_t len2 = strlen(str2);

  vector<vector<size_t> > dp(len1, vector<size_t>(len2, 0));

  for (int i = 0; i < len1; i++) {
    for (int j = 0; j < len2; j++) {
      size_t val = 0;
      if (str1[i] == str2[j]) {
	if (i - 1 >= 0 && j - 1 >= 0)
	  val = dp[i-1][j-1] + 1;
	else 
	  val = 1;
      }
      
      if (i - 1 >= 0) {
	val = max(val, dp[i-1][j]);
      }
      
      if (j - 1 >= 0) {
	val = max(val, dp[i][j-1]);
      }

      dp[i][j] = val;
    }
  }

  return dp[len1-1][len2-1];
}



int main() {
  cout << "Testing Longest Common Subsequence" << endl;
  cout << lcs("BDCABA", "ABCBDAB") << " == 4" << endl;
  
  return 0;
}
